package leetcode;

import java.util.*;

public class LC_heap {
    public static void main(String[] args) {
        LC_heap lcHeap = new LC_heap();
        System.out.println(lcHeap.findKthLargest(new int[]{3,2,1,5,6,4},2));
        System.out.println(Arrays.toString(lcHeap.topKFrequent(new int[]{4,1,-1,2,-1,2,3}, 2)));
        System.out.println(Arrays.toString(lcHeap.topKFrequent(new int[]{3, 2, 2, 5, 6, 4}, 1)));
    }
    /*
        LeetCode 215题
        给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     */
    public int findKthLargest(int[] nums, int k) {
        int max = nums[0], min = nums[0];
        for (int num : nums) {
            if (num > max) max = num;
            else if (num < min) min = num;
        }
        int[] temp = new int[max - min + 1];
        for (int num : nums) {
            temp[num - min]++;
        }
        System.out.println(Arrays.toString(temp));
        for (int i = temp.length - 1; i >= 0; i--) {
            k -= temp[i];
            if (k <= 0) return i+min;
        }
        return -1;
    }
    /*
        LeetCode 347题
        给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 统计频率
        for (int num : nums) {
            Integer ii = map.getOrDefault(num, 0);
            map.put(num, ++ii);
        }
        // 通过排序队列将频率小的轶
        Queue<Integer> queue = new PriorityQueue<>(Comparator.comparing(map::get));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() < k) queue.add(entry.getKey());
            else if (map.get(entry.getKey()) > map.get(queue.peek())){
                queue.remove();
                queue.add(entry.getKey());
            }
        }
        int[] ans = new int[k];
        int i = 0;
        while(!queue.isEmpty()){
            ans[i] = queue.remove();
            i++;
        }
        return ans;
    }
    /*
        LeetCode 295题
        中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
     */
    class MedianFinder {
        Queue<Integer> left = new PriorityQueue<>(Comparator.comparing(a -> -a));
        Queue<Integer> right = new PriorityQueue<>();
        public MedianFinder() {

        }

        public void addNum(int num) {
            if (left.isEmpty() || num <= left.peek()){
                left.add(num);
                if (left.size()-1 > right.size()){
                    right.add(left.poll());
                }
            }else {
                right.add(num);
                if (right.size() > left.size()){
                    left.add(right.poll());
                }
            }
        }

        public double findMedian() {
            if (left.size() > right.size()) return left.poll();
            return (double) (left.peek() + right.peek()) /2;
        }
    }
}
